//arithmetic practice

//bubble sort_冒泡
let bubbleSort = (arr = []) => {
    let length = arr.length;
    for (let i = 0; i < length - 1; i++) {
        for (let j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    return arr;
}

//quick sort_快速排序
let quickSort = (arr = []) => {
    if (arr.length <= 1) {
        return arr
    }

    var midIndex = Math.floor(arr.length / 2);
    var midValue = arr.splice(midIndex, 1)[0];

    var left = [];
    var right = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midValue) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }

    return quickSort(left).concat([midValue], quickSort(right));
}

//insert sort_插入排序
let insertSort = (arr = []) => {
    var length = arr.length;

    for (let i = 1; i < length; i++) {
        if (arr[i - 1] > arr[i]) {
            //取出无序数组当前需排序的元素
            var guard = arr[i];

            //记录有序数组的最后一个角标
            var j = i - 1;
            //当前需要遍历之前有序队列，比较插入guard
            while (j >= 0 && guard < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = guard; //插入
        }
    }
    return arr;
}

//binary Search_折半查找法 _前提传入的数组是有序的
//1.递归查找
let binarySearch_rc = (arr, dest, start, end) => {
    var end = end || arr.length - 1;
    var start = start || 0;
    var m = Math.floor((end + start) / 2);
    if (arr[m] == dest) {
        return m
    }
    if (dest > arr[m]) {
        return binarySearch_rc(arr, dest, m + 1, end)
    } else {
        return binarySearch_rc(arr, dest, 0, m - 1);
    }
    return false;
}


//2.非递归查找
let binarySearch = (arr = [], dest) => {
    var h = arr.length - 1;
    var l = 0;
    while (l <= h) {
        var m = Math.floor((h + l) / 2);
        if (arr[m] == dest) {
            return m;
        }
        if (dest > arr[m]) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }
    return flase;
}

//selectSort_选择排序
let selectSort = (arr = []) => {
    let length = arr.length;
    for (let i = 0; i < length - 1; i++) {
        let maxIndex = i;
        for (let j = i + 1; j < length; j++) {
            //找最大值
            if (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }
        //比较完了之后进行数据交换。
        [arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
    }
    return arr;
}

//构造回文
let getPlalindrome = (str) => {
    //转化成数组
    var strArr = str.split('');
    var len = strArr.length;
    var newArr = [];
    var start = 0,
        end = 0,
        max = 0,
        obj = {};

    for (var i = 0; i < len - 1; i++) {
        for (var j = i + 1; j < len; j++) {
            if (strArr[i] == strArr[j]) {
                end = j;
                if((j - i) > max) {
                    obj.max = (j - i);
                    obj.start = i;
                    obj.end = j;
                }
            }
        }
    }

    console.log(obj, str);
}

export default {
    bubbleSort,
    quickSort,
    insertSort,
    binarySearch,
    binarySearch_rc,
    selectSort,
    getPlalindrome
}